package com.sourcetrip.algorithm.unionfind;

/**
 * @author: ZhouBert
 * @date: 2021/1/5
 * @description: 并查集（以 Quick Union 的思路实现）
 * --
 * 听课后，在 UnionFindWithQuickUnionV0 的基础上进行【基于子树高度的优化】
 * 那究竟如何完成从上至下的寻找呢？感觉除非增加对下的引用，不然就要 O(n) 去整理遍历数组了。
 * --
 * 看来最后不是按照上面的设计，而是增加一个数组 array ，array[index] 记录 根节点为 index 的树的高度。
 * 【到现在为止，有很多的 数组的奇特应用，eg.二叉堆，计数排序，并查集】
 */
public class UnionFindWithQuickUnionV2 extends UnionFindWithQuickUnionV0 {
	/**
	 * 记录 树的高度
	 */
	private int[] heightArray = null;

	/**
	 * 构建固定容量的并查集
	 * 默认初始 parents 的元素的根节点指向自身，这样表示每个元素都是独立的集合
	 *
	 * @param capacity 并查集的容量
	 */
	public UnionFindWithQuickUnionV2(int capacity) {
		super(capacity);

		heightArray = new int[capacity];
		//默认每个高度都是 1
		for (int i = 0; i < capacity; i++) {
			heightArray[i] = 1;
		}
	}


	/**
	 * 只有当 h1==h2 时才进行高度的改变
	 * @param v1
	 * @param v2
	 */
	@Override
	public void union(int v1, int v2) {
		int p1 = locate(v1);
		int p2 = locate(v2);
		if (p1 == p2) {
			return;
		}
		int h1 = heightArray[p1];
		int h2 = heightArray[p2];
		if (h1 >= h2) {
			//将矮的依附到高的根节点
			parents[p2] = p1;
			if (h1 == h2) {
				heightArray[p1]++;
			}
		} else {
			parents[p1] = p2;
		}
	}
}
